/**17. 电话号码的字母组合
 * - 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * - 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 */
export function letterCombinations(digits: string = '23'): string[] {
    if (!digits) return []
    /**存储数字与字符串的映射 */
    const map: Record<string, string> = {
        '0': "",
        '1': "",
        '2': "abc",
        '3': "def",
        '4': "ghi",
        '5': "jkl",
        '6': "mno",
        '7': "pqrs",
        '8': "tuv",
        '9': "wxyz",
    }
    const res: string[] = []
    let item = ''
    /**回溯
     * @param index 当前递归到第几个数字了
     */
    const back = (index: number) => {
        if (index === digits.length) {
            res.push(item)
            return
        }
        //遍历当前数字对应的字符
        for (let i = 0; i < map[digits[index]].length; i++) {
            item += map[digits[index]][i]//赋值
            back(index + 1) //处理下一个
            item = item.slice(0, -1)//回溯
        }
    }
    back(0)
    return res
}
/**22. 括号生成
 * - 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * - 示例：输入：n = 3
 * - 输出：["((()))","(()())","(())()","()(())","()()()"]
 */
export function generateParenthesis(n: number = 3): string[] {
    //回溯。 目的就是在  已有括号中，的每一个位置，插入一个‘()’，然后递归，回溯
    //但是这样得得到的结果会很多重复 ，比如 (())，在索引1处插入和在-1处插入，得到的结果其实是一样的，最终需要去重
    // 优化？ 需要剪枝吧？？
    const res: string[] = []
    const maxLength = n * 2
    let path = '()'
    const back = (count: number) => {
        if (path.length === maxLength) {
            res.push(path)
            return
        }
        for (let i = 0; i < path.length; i++) {
            let temp = path
            path = path.slice(0, i) + '()' + path.slice(i) //插入
            back(count - 1)//递归
            path = temp //回溯
        }
    }
    back(n - 1) //因为path里已经先放入一个括号了，所以这里从n-1开始
    return [...new Set(res)] //去重
}
/**43. 全排列 */
export function permute(nums: number[]): number[][] {
    const res: number[][] = []
    const item: number[] = [];
    const used = new Set<number>() //used数组放在外面，因为去重是去重 垂直方向的（递归方向），记得回溯（如果used放在for循环前面，就不用回溯）
    function back() {
        if (item.length == nums.length) {
            res.push([...item])
            return
        }
        for (let i = 0; i < nums.length; i++) {//因为要全排列，所以是从0开始，而不是之前写的startIndex
            if (used.has(nums[i])) continue
            used.add(nums[i])
            item.push(nums[i])
            back()
            item.pop()
            used.delete(nums[i])
        }
    }
    back()
    return res
};
/**93. 复原 IP 地址
 * - 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * - 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 */
export function restoreIpAddresses(s: string): string[] {
    const res: string[] = []
    const item: string[] = []
    const isValid = (str: string) => {
        const num = Number(str)
        //ip每个部分的合法： 无前导0、1~3位数、
        if (str.length > 3 || str.length === 0 || isNaN(num) || num > 255 || (str.length > 1 && str[0] === '0')) return false
        return true
    }
    const back = (startIndex: number) => {
        if (item.length === 4 && startIndex >= s.length) {//确保整个s遍历完了才可以
            res.push(item.join('.'))
            return
        }
        if (item.length === 4 || startIndex >= s.length) return;//防止越界
        //注意这里的i初始化需要+1(结束条件也需要往后推)，因为下面裁剪需要。
        for (let i = startIndex + 1; i <= Math.min(s.length, startIndex + 3); i++) {//这里剪枝，因为最长三个字符
            const str = s.substring(startIndex, i)
            if (isValid(str)) {
                item.push(str)
                back(i)//继续切割 （这里不用+1，因为在for循环里加了）
                item.pop()
            } else {
                break //一旦不合法就退出循环 （因为后面的都是错的了）
            }
        }
    }
    back(0)
    return res
}
/**1048. 最长字符串链 */
export function longestStrChain(words: string[]): number {
    // 逆向思维：从长度更长的单词，删除某个字母，查看是否在words里有前身

    // 递归回溯 + 记忆Map ：  击败情况：速度100%，内存0%
    const set = new Set(words)
    const used = new Map<string, number>() //记录当前单词开头的词链长度 
    /**递归：从当前字符串开始往下寻找前身，并顺带记录每个字符串的词链长度
     * @param str 当前字符串
     * @param preLength 当前字符串的前身共有几个
     * @returns str的词链长度
     */
    const recursion = (str: string, preLength: number) => {
        if (used.has(str)) {
            return used.get(str)!
        }
        let maxLength = preLength
        for (let i = 0; i < str.length; i++) {
            const nextStr = str.slice(0, i) + str.slice(i + 1)
            if (set.has(nextStr)) {
                maxLength = Math.max(maxLength, recursion(nextStr, preLength + 1)) //这里不是length++，而是length+1，是回溯，方便下一个i能正常使用length  
            }
        }
        used.set(str, maxLength - preLength + 1) //这里记录当前单词的词链长度 （maxLength是包含了上一个单词的长度，所以需要减去length。+1代表当前的单词也算长度）
        return maxLength
    }
    words.sort((a, b) => b.length - a.length).forEach((k) => recursion(k, 0))//先逆序排序，有利于后序短的单词触发记忆  
    // 这里used已经记录了所有单词的词链长度，所以直接遍历计算即可
    let max = 0
    used.forEach((v) => max = Math.max(max, v))
    return max

}
/** 2698. 求一个整数的惩罚数
 * - 给你一个正整数 n ，请你返回 n 的 惩罚数 。
 * - n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：
 * 1. 1 <= i <= n
 * 2. i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i
 */
export function punishmentNumber(n: number): number {
    /**回溯
     * @param num 当前的数字字符串
     * @param target 目标值为0且num为空串，代表成功  （这样可以节省一个变量的开销）
     * @returns 
     */
    const backtrack = (num: string, target: number) => {
        if (target === 0 && num.length === 0) return true //num为空串，确保是最后一个数了
        if (num.length === 0 || target < 0 || isNaN(target)) return false //如果target不符合条件就false
        // console.log(num, target);


        //for循环遍历横向。 比如 123  -> 1、12、123
        for (let i = 0; i <= num.length; i++) {
            //递归纵向遍历： 比如 123， 上一次选了1，那么这一次就判断 23 怎么选。 target减去当前的数
            if (backtrack(num.slice(i), target - parseInt(num.slice(0, i)))) {
                // console.log('@@', i, num.slice(i), '_', num.slice(0, i), target);
                return true
            }
        }
        return false //最终还不成功就false
    }

    let res = 0
    for (let i = 1; i <= n; i++) {
        const square = i * i
        if (backtrack(String(square), i)) {
            console.log('————————', i, '成功了');
            res += square
        }

    }
    return res
}